【图论笔记】权转移法（0）：一个简单的例子

---

目录

• 1. 简介
• 2. 一个例题
• 返回【图论笔记】

---

1. 简介

权转移法，英文名为Discharging Method，直译即“电荷释放法”．在图论中，它已经有了超过一百的历史了．其最著名的应用是证明了四色定理，也就是证明了嵌入在平面上的图的色数至多为$4$（其实这个说法稍微有些不严谨）．然而，即使对于大多数图论工作者，这种方法仍然十分神秘．

我们这篇学习指导的目的在于让学习者了解权转移法的使用方法，从而让更多的人能理解和使用这种方法．

为了解释权转移法，我们将会以一个简单的题目为例．在此之前，我们先来明确一些术语．

• 如果一个简单平面图的每个面的边界都是$3$-圈，我们称这个简单平面图是一个平面三角剖分图．

• 如果顶点$v$的度等于$d$，那么我们称$v$为 $d$-顶点；如果$v$的度至少$d$（至多$d$），那么我们称$v$为 $d^+$-顶点 （$d^-$-顶点）．

• 设$P=v_1v_2\dots v_t$是图$G$的一条 $t$-路（即$t$个顶点的路，虽然有的学者习惯用$t$-路表示长度为$t$的路，我们这里为了方便叙述，将$t$个顶点的路称为$t$-路）．

  • 如果$d_G(v_i)=d_i$，其中$i=1,2,\dots,t$，那么我们称路$P$是一个 $(d_1,d_2,\dots,d_t)$-路；
  • 特别地，如果$d_G(v_i)\ge d_i$或$\le d_i$，那么上述数组中的$d_i$可以相应地换成$d_i^+$或$d_i^-$．

---

2. 一个例题

例题1 如果平面三角剖分图$G$的最小度为$5$，那么$G$包含一条$(5,5)$-边或一条$(5,6)$-边．

证明. 首先，我们假设结论是不成立的，而$G$是一个反例．这是权转移法的第一步：假设存在反例．

接下来，我们对$G$的每个顶点$v$赋予一个数，记作$ch_0(v)$，一般称之为$v$的初始电荷量；具体说来，我们这里令$ch_0(v)=d(v)-6$，$v\in V(G)$（我们一般说：给$v$赋予$d(v)-6$个单位的初始电荷量）．

然后，再给每个面$f$赋予$2d(f)-6$个单位的初始电荷，即$ch_0(f)=2d(f)-6$．由于$G$是三角剖分图，所以实际上每个面的初始电荷量为零．

现在我们考虑图$G$上的总的初始电荷量，$\sum_{x\in V(G)\cup F(G)}ch_0(x)=2e(G)-6v(G)+4e(G)-6f(G)=-12<0.$这就是权转移法的第二步：赋予初始电荷量．

然后是权转移法的第三步：转移电荷（即假定电荷是可以按我们的意志移动的）．

为此我们需要制定一个放电规则（discharging rules）．我们的放电规则只有一条，那就是：每个$5$-顶点从它的邻点拿走$1/5$单位的电量．

我们记放电之后每个顶点和面的电荷量为$ch_1(\cdot)$．显然，对每个面$f$，$ch_1(f)=ch_0(f)=0$．考虑顶点$v$．因为$G$是一个反例，所以每个$5$-顶点没有$6^-$-邻点，每一个$6$-顶点也没有$5$-邻点。因此如果$d(v)=5,6$，那么$ch_1(v)=0$．如果$d(v)\ge7$，由于$G$是三角剖分图且没有$(5,5)$-边，所以$v$的$5$-邻点个数不超过$\frac{1}{2}d(v)$，所以$ch_1(v)\ge d(v)-6-\frac{1}{5}\cdot\frac{1}{2}d(v)=3/10>0.$

可见，经过放电后，每个顶点和面的电荷量都是非负。但是请注意，我们的放电并不改变总电荷量，所以最终的总电荷量与初始的总电荷量应该是相等的，也就是负的。这是个矛盾．

其实上述结论可以加强．

• 我们称每个面的边界都是3-圈的平面图为平面半三角剖分图，注意平面三角剖分图是简单图，但平面半三角剖分图允许出现平行边（请大家思考一下为什么有可能出现一个平面图每个面都是3-面同时还有平行边的现象）．

上述例题可以加强到平面半三角剖分图．

上述证明还可以简化一下．因为平面图$G$上必有$e(G)\le 3v(G)-6$．其等号成立当且仅当$G$是平面半三角剖分图．
所以初始电荷量以及电荷量的计算可以简化．请大家自行尝试．

---

• 返回【图论笔记】